package Tree.threadedbinarytree;

public class ThreadedBinaryTreeDemo {

  public static void main(String[] args) {
    /*
      1
   3      6
 8  10  14
 中序遍历的结果：8 3 10 1 14 6
     */
    HeroNode root = new HeroNode(1,"tom");
    HeroNode node2 = new HeroNode(3, "jack");
    HeroNode node3 = new HeroNode(6, "smith");
    HeroNode node4 = new HeroNode(8, "mary");
    HeroNode node5 = new HeroNode(10,"king");
    HeroNode node6 = new HeroNode(14,"dim");

//    创建二叉树
    root.setLeft(node2);
    root.setRight(node3);
    node2.setLeft(node4);
    node2.setRight(node5);
    node3.setLeft(node6);

    ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
//    构造线索化二叉树
    threadedBinaryTree.setRoot(root);
    threadedBinaryTree.threadedNodes(root);

    System.out.println("10号的前驱节点：" + node5.getLeft());//3
    System.out.println("10号的后继节点：" + node5.getRight());//1

    threadedBinaryTree.threadedList();


  }
}

class HeroNode{
  private int no;
  private String name;
  private HeroNode left;
  private HeroNode right;

  //说明
  //1.如果leftType =表示指向的是左子树，如果1则表示指向前驱结点
  //2．如果rightType ==表示指向是右子树，如果1表示指向后继结点
  private int leftType;
  private int rightType;

  public int getLeftType() {
    return leftType;
  }

  public void setLeftType(int leftType) {
    this.leftType = leftType;
  }

  public int getRightType() {
    return rightType;
  }

  public void setRightType(int rightType) {
    this.rightType = rightType;
  }

  public HeroNode(int no, String name) {
    this.no = no;
    this.name = name;
  }

  public int getNo() {
    return no;
  }

  public void setNo(int no) {
    this.no = no;
  }

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public HeroNode getLeft() {
    return left;
  }

  public void setLeft(HeroNode left) {
    this.left = left;
  }

  public HeroNode getRight() {
    return right;
  }

  public void setRight(HeroNode right) {
    this.right = right;
  }

  @Override
  public String toString() {
    return "HeroNode{" +
            "no=" + no +
            ", name='" + name + '\'' +
            '}';
  }
}

//实现了线索化功能的二叉树
class ThreadedBinaryTree{
  private HeroNode root;

  //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
  private HeroNode pre = null;


  public void setRoot(HeroNode root) {
    this.root = root;
  }

//  对二叉树进行中序线索化的方法
  public void threadedNodes(HeroNode node){
    if (node == null){
      return;
    }
//    对左子树实现线索化
    threadedNodes(node.getLeft());
//    对当前节点实现线索化
    //8结点的.left = null ，
    //8结点的.leftType = 1
     if(node.getLeft() == null) {
    //让当前结点的左指针指向前驱结点
       node.setLeft(pre) ;
    //修改当前结点的左指针的类型,指向前驱结点
       node.setLeftType(1);
     }
    //处理后继结点
    if (pre != null && pre.getRight() == null){
      //让前驱结点的右指针指向当前结点
      pre.setRight(node);
      //修改前驱结点的右指针类型
      pre.setRightType(1);
     }
    //每处理一个结点后,让当前结点是下一个结点的前驱结点
    pre = node;



//    对右子树实现线索化
    threadedNodes(node.getRight());

  }

//  线索化二叉树的遍历
  public void threadedList(){
    HeroNode node = root;
    while (node != null){
//      找到第一个leftType为1的节点，即8
      while (node.getLeftType() == 0){
        node = node.getLeft();
      }
//      打印该节点
      System.out.println(node);

      while (node.getRightType() == 1){
        node  = node.getRight();
        System.out.println(node);
      }
      node = node.getRight();
    }
  }
}
